reducible.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397
  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. bool trivialGraph(BB *G)
  20. {
  21. return G->edges.empty();
  22. }
  23. /* Returns whether the graph is a trivial graph or not */
  24. /* Returns the first element in the queue Q, and removes this element
  25. * from the list. Q is not an empty queue. */
  26. static BB *firstOfQueue (queue &Q)
  27. {
  28. assert(!Q.empty());
  29. BB *res=*Q.begin();
  30. Q.pop_front();
  31. return res;
  32. }
  33. /* Appends pointer to node at the end of the queue Q if node is not present
  34. * in this queue. Returns the queue node just appended. */
  35. queue::iterator appendQueue (queue &Q, BB *node)
  36. {
  37. auto iter=std::find(Q.begin(),Q.end(),node);
  38. if(iter!=Q.end())
  39. return iter;
  40. Q.push_back(node);
  41. iter=Q.end();
  42. --iter;
  43. return iter;
  44. }
  45. /* Returns the next unprocessed node of the interval list (pointed to by
  46. * pI->currNode). Removes this element logically from the list, by updating
  47. * the currNode pointer to the next unprocessed element. */
  48. BB *interval::firstOfInt ()
  49. {
  50. auto pq = currNode;
  51. if (pq == nodes.end())
  52. return (NULL);
  53. ++currNode;
  54. return *pq;
  55. }
  56. /* Appends node @node to the end of the interval list @pI, updates currNode
  57. * if necessary, and removes the node from the header list @pqH if it is
  58. * there. The interval header information is placed in the field
  59. * node->inInterval.
  60. * Note: nodes are added to the interval list in interval order (which
  61. * topsorts the dominance relation). */
  62. static void appendNodeInt (queue &pqH, BB *node, interval *pI)
  63. {
  64. queue::iterator pq; /* Pointer to current node of the list */
  65. /* Append node if it is not already in the interval list */
  66. pq = appendQueue (pI->nodes, node);
  67. /* Update currNode if necessary */
  68. if (pI->currNode == pI->nodes.end())
  69. pI->currNode = pq;
  70. /* Check header list for occurrence of node, if found, remove it
  71. * and decrement number of out-edges from this interval. */
  72. if (node->beenOnH && !pqH.empty())
  73. {
  74. auto found_iter=std::find(pqH.begin(),pqH.end(),node);
  75. if(found_iter!=pqH.end())
  76. {
  77. pI->numOutEdges -= (byte)(*found_iter)->inEdges.size() - 1;
  78. pqH.erase(found_iter);
  79. }
  80. }
  81. /* Update interval header information for this basic block */
  82. node->inInterval = pI;
  83. }
  84. /* Finds the intervals of graph derivedGi->Gi and places them in the list
  85. * of intervals derivedGi->Ii.
  86. * Algorithm by M.S.Hecht. */
  87. void derSeq_Entry::findIntervals (Function *c)
  88. {
  89. interval *pI, /* Interval being processed */
  90. *J; /* ^ last interval in derivedGi->Ii */
  91. BB *h, /* Node being processed */
  92. *header, /* Current interval's header node */
  93. *succ; /* Successor basic block */
  94. Int i; /* Counter */
  95. queue H; /* Queue of possible header nodes */
  96. boolT first = TRUE; /* First pass through the loop */
  97. appendQueue (H, Gi); /* H = {first node of G} */
  98. Gi->beenOnH = TRUE;
  99. Gi->reachingInt = BB::Create(0,"",c); /* ^ empty BB */
  100. /* Process header nodes list H */
  101. while (!H.empty())
  102. {
  103. header = firstOfQueue (H);
  104. pI = new interval;
  105. pI->numInt = (byte)numInt++;
  106. if (first) /* ^ to first interval */
  107. Ii = J = pI;
  108. appendNodeInt (H, header, pI); /* pI(header) = {header} */
  109. /* Process all nodes in the current interval list */
  110. while ((h = pI->firstOfInt()) != NULL)
  111. {
  112. /* Check all immediate successors of h */
  113. for (i = 0; i < h->edges.size(); i++)
  114. {
  115. succ = h->edges[i].BBptr;
  116. succ->inEdgeCount--;
  117. if (succ->reachingInt == NULL) /* first visit */
  118. {
  119. succ->reachingInt = header;
  120. if (succ->inEdgeCount == 0)
  121. appendNodeInt (H, succ, pI);
  122. else if (! succ->beenOnH) /* out edge */
  123. {
  124. appendQueue (H, succ);
  125. succ->beenOnH = TRUE;
  126. pI->numOutEdges++;
  127. }
  128. }
  129. else /* node has been visited before */
  130. if (succ->inEdgeCount == 0)
  131. {
  132. if (succ->reachingInt == header || succ->inInterval == pI) /* same interval */
  133. {
  134. if (succ != header)
  135. appendNodeInt (H, succ, pI);
  136. }
  137. else /* out edge */
  138. pI->numOutEdges++;
  139. }
  140. else if (succ != header && succ->beenOnH)
  141. pI->numOutEdges++;
  142. }
  143. }
  144. /* Link interval I to list of intervals */
  145. if (! first)
  146. {
  147. J->next = pI;
  148. J = pI;
  149. }
  150. else /* first interval */
  151. first = FALSE;
  152. }
  153. }
  154. /* Displays the intervals of the graph Gi. */
  155. static void displayIntervals (interval *pI)
  156. {
  157. queue::iterator nodePtr;
  158. while (pI)
  159. {
  160. nodePtr = pI->nodes.begin();
  161. printf (" Interval #: %ld\t#OutEdges: %ld\n", pI->numInt, pI->numOutEdges);
  162. while (nodePtr!=pI->nodes.end())
  163. {
  164. if ((*nodePtr)->correspInt == NULL) /* real BBs */
  165. printf (" Node: %ld\n", (*nodePtr)->begin());
  166. else /* BBs represent intervals */
  167. printf (" Node (corresp int): %d\n", (*nodePtr)->correspInt->numInt);
  168. ++nodePtr;
  169. }
  170. pI = pI->next;
  171. }
  172. }
  173. /* Allocates space for a new derSeq node. */
  174. static derSeq_Entry *newDerivedSeq()
  175. {
  176. return new derSeq_Entry;
  177. }
  178. /* Frees the storage allocated for the queue q*/
  179. void freeQueue (queue &q)
  180. {
  181. q.clear();
  182. }
  183. /* Frees the storage allocated for the interval pI */
  184. static void freeInterval (interval **pI)
  185. {
  186. interval *Iptr;
  187. while (*pI)
  188. {
  189. (*pI)->nodes.clear();
  190. Iptr = *pI;
  191. *pI = (*pI)->next;
  192. delete (Iptr);
  193. }
  194. }
  195. /* Frees the storage allocated by the derived sequence structure, except
  196. * for the original graph cfg (derivedG->Gi). */
  197. void freeDerivedSeq(derSeq &derivedG)
  198. {
  199. derivedG.clear();
  200. }
  201. derSeq_Entry::~derSeq_Entry()
  202. {
  203. freeInterval (&Ii);
  204. // if(Gi && Gi->nodeType == INTERVAL_NODE)
  205. // freeCFG (Gi);
  206. }
  207. /* Finds the next order graph of derivedGi->Gi according to its intervals
  208. * (derivedGi->Ii), and places it in derivedGi->next->Gi. */
  209. bool Function::nextOrderGraph (derSeq *derivedGi)
  210. {
  211. interval *Ii; /* Interval being processed */
  212. BB *BBnode, /* New basic block of intervals */
  213. *curr, /* BB being checked for out edges */
  214. *succ /* Successor node */
  215. ;
  216. //queue *listIi; /* List of intervals */
  217. Int i, /* Index to outEdges array */
  218. j; /* Index to successors */
  219. boolT sameGraph; /* Boolean, isomorphic graphs */
  220. /* Process Gi's intervals */
  221. derSeq_Entry &prev_entry(derivedGi->back());
  222. derivedGi->push_back(derSeq_Entry());
  223. derSeq_Entry &new_entry(derivedGi->back());
  224. Ii = prev_entry.Ii;
  225. sameGraph = TRUE;
  226. BBnode = 0;
  227. std::vector<BB *> bbs;
  228. while (Ii)
  229. {
  230. i = 0;
  231. bbs.push_back(BB::Create(-1, -1, INTERVAL_NODE, Ii->numOutEdges, this));
  232. BBnode = bbs.back();
  233. BBnode->correspInt = Ii;
  234. const queue &listIi(Ii->nodes);
  235. /* Check for more than 1 interval */
  236. if (sameGraph && (listIi.size()>1))
  237. sameGraph = FALSE;
  238. /* Find out edges */
  239. if (BBnode->edges.size() > 0)
  240. {
  241. for(BB *curr : listIi)
  242. {
  243. for (j = 0; j < curr->edges.size(); j++)
  244. {
  245. succ = curr->edges[j].BBptr;
  246. if (succ->inInterval != curr->inInterval)
  247. BBnode->edges[i++].intPtr = succ->inInterval;
  248. }
  249. }
  250. }
  251. /* Next interval */
  252. Ii = Ii->next;
  253. }
  254. /* Convert list of pointers to intervals into a real graph.
  255. * Determines the number of in edges to each new BB, and places it
  256. * in numInEdges and inEdgeCount for later interval processing. */
  257. curr = new_entry.Gi = bbs.front();
  258. for(BB *curr : bbs)
  259. {
  260. for(TYPEADR_TYPE &edge : curr->edges)
  261. {
  262. BBnode = new_entry.Gi; /* BB of an interval */
  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. }