reducible.cpp 12 KB

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