reducible.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420
  1. /********************************************************************
  2. * Checks for reducibility of a graph by intervals, and
  3. * constructs an equivalent reducible graph if one is not found.
  4. * (C) Cristina Cifuentes
  5. ********************************************************************/
  6. #include "dcc.h"
  7. #include <stdio.h>
  8. #ifdef __BORLAND__
  9. #include <alloc.h>
  10. #else
  11. #include <malloc.h> /* For free() */
  12. #endif
  13. #include <string.h>
  14. static Int numInt; /* Number of intervals */
  15. #define nonEmpty(q) (q != NULL)
  16. /* Returns whether the queue q is empty or not */
  17. #define trivialGraph(G) (G->numOutEdges == 0)
  18. /* Returns whether the graph is a trivial graph or not */
  19. static BB *firstOfQueue (queue **Q)
  20. /* Returns the first element in the queue Q, and removes this element
  21. * from the list. Q is not an empty queue. */
  22. { queue *elim;
  23. BB *first;
  24. elim = *Q; /* Pointer to first node */
  25. first = (*Q)->node; /* First element */
  26. *Q = (*Q)->next; /* Pointer to next node */
  27. free (elim); /* Free storage */
  28. return (first);
  29. }
  30. queue *appendQueue (queue **Q, BB *node)
  31. /* Appends pointer to node at the end of the queue Q if node is not present
  32. * in this queue. Returns the queue node just appended. */
  33. { queue *pq, *l;
  34. pq = allocStruc(queue);
  35. pq->node = node;
  36. pq->next = NULL;
  37. if (Q)
  38. if (*Q)
  39. {
  40. for (l = *Q; l->next && l->node != node; l = l->next)
  41. ;
  42. if (l->node != node)
  43. l->next = pq;
  44. }
  45. else /* (*Q) == NULL */
  46. *Q = pq;
  47. return (pq);
  48. }
  49. static BB *firstOfInt (interval *pI)
  50. /* Returns the next unprocessed node of the interval list (pointed to by
  51. * pI->currNode). Removes this element logically from the list, by updating
  52. * the currNode pointer to the next unprocessed element. */
  53. { queue *pq;
  54. pq = pI->currNode;
  55. if (pq == NULL)
  56. return (NULL);
  57. pI->currNode = pq->next;
  58. return (pq->node);
  59. }
  60. static queue *appendNodeInt (queue *pqH, BB *node, interval *pI)
  61. /* Appends node node to the end of the interval list I, updates currNode
  62. * if necessary, and removes the node from the header list H if it is
  63. * there. The interval header information is placed in the field
  64. * node->inInterval.
  65. * Note: nodes are added to the interval list in interval order (which
  66. * topsorts the dominance relation). */
  67. { queue *pq, /* Pointer to current node of the list */
  68. *prev; /* Pointer to previous node in the list */
  69. /* Append node if it is not already in the interval list */
  70. pq = appendQueue (&pI->nodes, node);
  71. /* Update currNode if necessary */
  72. if (pI->currNode == NULL)
  73. pI->currNode = pq;
  74. /* Check header list for occurrence of node, if found, remove it
  75. * and decrement number of out-edges from this interval. */
  76. if (node->beenOnH && pqH)
  77. {
  78. prev = pqH;
  79. for (pq = prev; pq && pq->node != node; pq = pq->next)
  80. prev = pq;
  81. if (pq == prev)
  82. {
  83. pqH = pqH->next;
  84. pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
  85. }
  86. else if (pq)
  87. {
  88. prev->next = pq->next;
  89. pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
  90. }
  91. }
  92. /* Update interval header information for this basic block */
  93. node->inInterval = pI;
  94. return (pqH);
  95. }
  96. static void findIntervals (derSeq *derivedGi)
  97. /* Finds the intervals of graph derivedGi->Gi and places them in the list
  98. * of intervals derivedGi->Ii.
  99. * Algorithm by M.S.Hecht. */
  100. { interval *pI, /* Interval being processed */
  101. *J; /* ^ last interval in derivedGi->Ii */
  102. BB *h, /* Node being processed */
  103. *header, /* Current interval's header node */
  104. *succ; /* Successor basic block */
  105. Int i; /* Counter */
  106. queue *H; /* Queue of possible header nodes */
  107. boolT first = TRUE; /* First pass through the loop */
  108. H = appendQueue (NULL, derivedGi->Gi); /* H = {first node of G} */
  109. derivedGi->Gi->beenOnH = TRUE;
  110. derivedGi->Gi->reachingInt = allocStruc(BB); /* ^ empty BB */
  111. memset (derivedGi->Gi->reachingInt, 0, sizeof(BB));
  112. /* Process header nodes list H */
  113. while (nonEmpty (H))
  114. {
  115. header = firstOfQueue (&H);
  116. pI = allocStruc(interval);
  117. memset (pI, 0, sizeof(interval));
  118. pI->numInt = (byte)numInt++;
  119. if (first) /* ^ to first interval */
  120. derivedGi->Ii = J = pI;
  121. H = appendNodeInt (H, header, pI); /* pI(header) = {header} */
  122. /* Process all nodes in the current interval list */
  123. while ((h = firstOfInt (pI)) != NULL)
  124. {
  125. /* Check all immediate successors of h */
  126. for (i = 0; i < h->numOutEdges; i++)
  127. {
  128. succ = h->edges[i].BBptr;
  129. succ->inEdgeCount--;
  130. if (succ->reachingInt == NULL) /* first visit */
  131. {
  132. succ->reachingInt = header;
  133. if (succ->inEdgeCount == 0)
  134. H = appendNodeInt (H, succ, pI);
  135. else if (! succ->beenOnH) /* out edge */
  136. {
  137. appendQueue (&H, succ);
  138. succ->beenOnH = TRUE;
  139. pI->numOutEdges++;
  140. }
  141. }
  142. else /* node has been visited before */
  143. if (succ->inEdgeCount == 0)
  144. {
  145. if (succ->reachingInt == header ||
  146. succ->inInterval == pI) /* same interval */
  147. {
  148. if (succ != header)
  149. H = appendNodeInt (H, succ, pI);
  150. }
  151. else /* out edge */
  152. pI->numOutEdges++;
  153. }
  154. else if (succ != header && succ->beenOnH)
  155. pI->numOutEdges++;
  156. }
  157. }
  158. /* Link interval I to list of intervals */
  159. if (! first)
  160. {
  161. J->next = pI;
  162. J = pI;
  163. }
  164. else /* first interval */
  165. first = FALSE;
  166. }
  167. }
  168. static void displayIntervals (interval *pI)
  169. /* Displays the intervals of the graph Gi. */
  170. { queue *nodePtr;
  171. while (pI)
  172. {
  173. nodePtr = pI->nodes;
  174. printf (" Interval #: %ld\t#OutEdges: %ld\n",
  175. pI->numInt, pI->numOutEdges);
  176. while (nodePtr)
  177. {
  178. if (nodePtr->node->correspInt == NULL) /* real BBs */
  179. printf (" Node: %ld\n", nodePtr->node->start);
  180. else /* BBs represent intervals */
  181. printf (" Node (corresp int): %d\n",
  182. nodePtr->node->correspInt->numInt);
  183. nodePtr = nodePtr->next;
  184. }
  185. pI = pI->next;
  186. }
  187. }
  188. static derSeq *newDerivedSeq()
  189. /* Allocates space for a new derSeq node. */
  190. { derSeq *pder;
  191. pder = allocStruc(derSeq);
  192. memset (pder, 0, sizeof(derSeq));
  193. return (pder);
  194. }
  195. static void freeQueue (queue **q)
  196. /* Frees the storage allocated for the queue q*/
  197. { queue *queuePtr;
  198. for (queuePtr = *q; queuePtr; queuePtr = *q)
  199. {
  200. *q = (*q)->next;
  201. free (queuePtr);
  202. }
  203. }
  204. static void freeInterval (interval **pI)
  205. /* Frees the storage allocated for the interval pI */
  206. { interval *Iptr;
  207. while (*pI)
  208. {
  209. freeQueue (&((*pI)->nodes));
  210. Iptr = *pI;
  211. *pI = (*pI)->next;
  212. free (Iptr);
  213. }
  214. }
  215. void freeDerivedSeq(derSeq *derivedG)
  216. /* Frees the storage allocated by the derived sequence structure, except
  217. * for the original graph cfg (derivedG->Gi). */
  218. { derSeq *derivedGi;
  219. while (derivedG)
  220. {
  221. freeInterval (&(derivedG->Ii));
  222. if (derivedG->Gi->nodeType == INTERVAL_NODE)
  223. freeCFG (derivedG->Gi);
  224. derivedGi = derivedG;
  225. derivedG = derivedG->next;
  226. free (derivedGi);
  227. }
  228. }
  229. static boolT nextOrderGraph (derSeq *derivedGi)
  230. /* Finds the next order graph of derivedGi->Gi according to its intervals
  231. * (derivedGi->Ii), and places it in derivedGi->next->Gi. */
  232. { interval *Ii; /* Interval being processed */
  233. BB *BBnode, /* New basic block of intervals */
  234. *curr, /* BB being checked for out edges */
  235. *succ, /* Successor node */
  236. derInt;
  237. queue *listIi; /* List of intervals */
  238. Int i, /* Index to outEdges array */
  239. j; /* Index to successors */
  240. boolT sameGraph; /* Boolean, isomorphic graphs */
  241. /* Process Gi's intervals */
  242. derivedGi->next = newDerivedSeq();
  243. Ii = derivedGi->Ii;
  244. sameGraph = TRUE;
  245. derInt.next = NULL;
  246. BBnode = &derInt;
  247. while (Ii) {
  248. i = 0;
  249. BBnode = newBB (BBnode, -1, -1, INTERVAL_NODE, Ii->numOutEdges, NULL);
  250. BBnode->correspInt = Ii;
  251. listIi = Ii->nodes;
  252. /* Check for more than 1 interval */
  253. if (sameGraph && listIi->next)
  254. sameGraph = FALSE;
  255. /* Find out edges */
  256. if (BBnode->numOutEdges > 0)
  257. while (listIi) {
  258. curr = listIi->node;
  259. for (j = 0; j < curr->numOutEdges; j++) {
  260. succ = curr->edges[j].BBptr;
  261. if (succ->inInterval != curr->inInterval)
  262. BBnode->edges[i++].intPtr = succ->inInterval;
  263. }
  264. listIi = listIi->next;
  265. }
  266. /* Next interval */
  267. Ii = Ii->next;
  268. }
  269. /* Convert list of pointers to intervals into a real graph.
  270. * Determines the number of in edges to each new BB, and places it
  271. * in numInEdges and inEdgeCount for later interval processing. */
  272. curr = derivedGi->next->Gi = derInt.next;
  273. while (curr) {
  274. for (i = 0; i < curr->numOutEdges; i++) {
  275. BBnode = derivedGi->next->Gi; /* BB of an interval */
  276. while (BBnode && curr->edges[i].intPtr != BBnode->correspInt)
  277. BBnode = BBnode->next;
  278. if (BBnode) {
  279. curr->edges[i].BBptr = BBnode;
  280. BBnode->numInEdges++;
  281. BBnode->inEdgeCount++;
  282. }
  283. else
  284. fatalError (INVALID_INT_BB);
  285. }
  286. curr = curr->next;
  287. }
  288. return (boolT)(! sameGraph);
  289. }
  290. static byte findDerivedSeq (derSeq *derivedGi)
  291. /* Finds the derived sequence of the graph derivedG->Gi (ie. cfg).
  292. * Constructs the n-th order graph and places all the intermediate graphs
  293. * in the derivedG list sequence. */
  294. { BB *Gi; /* Current derived sequence graph */
  295. Gi = derivedGi->Gi;
  296. while (! trivialGraph (Gi))
  297. {
  298. /* Find the intervals of Gi and place them in derivedGi->Ii */
  299. findIntervals (derivedGi);
  300. /* Create Gi+1 and check if it is equivalent to Gi */
  301. if (! nextOrderGraph (derivedGi))
  302. break;
  303. derivedGi = derivedGi->next;
  304. Gi = derivedGi->Gi;
  305. stats.nOrder++;
  306. }
  307. if (! trivialGraph (Gi))
  308. {
  309. freeDerivedSeq(derivedGi->next); /* remove Gi+1 */
  310. derivedGi->next = NULL;
  311. return FALSE;
  312. }
  313. findIntervals (derivedGi);
  314. return TRUE;
  315. }
  316. static void nodeSplitting (BB *G)
  317. /* Converts the irreducible graph G into an equivalent reducible one, by
  318. * means of node splitting. */
  319. {
  320. }
  321. void displayDerivedSeq(derSeq *derGi)
  322. /* Displays the derived sequence and intervals of the graph G */
  323. {
  324. Int n = 1; /* Derived sequence number */
  325. printf ("\nDerived Sequence Intervals\n");
  326. while (derGi)
  327. {
  328. printf ("\nIntervals for G%lX\n", n++);
  329. displayIntervals (derGi->Ii);
  330. derGi = derGi->next;
  331. }
  332. }
  333. void checkReducibility (PPROC pProc, derSeq **derivedG)
  334. /* Checks whether the control flow graph, cfg, is reducible or not.
  335. * If it is not reducible, it is converted into an equivalent reducible
  336. * graph by node splitting. The derived sequence of graphs built from cfg
  337. * are returned in the pointer *derivedG.
  338. */
  339. { byte reducible; /* Reducible graph flag */
  340. numInt = 1; /* reinitialize no. of intervals*/
  341. stats.nOrder = 1; /* nOrder(cfg) = 1 */
  342. *derivedG = newDerivedSeq();
  343. (*derivedG)->Gi = pProc->cfg;
  344. reducible = findDerivedSeq(*derivedG);
  345. if (! reducible) {
  346. pProc->flg |= GRAPH_IRRED;
  347. nodeSplitting (pProc->cfg);
  348. }
  349. }