reducible.cpp 12 KB

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